Trick 14: 為什麼要寫自己的亂數產生器

14th鐵人賽 typescript javascript 演算法遊戲開發

小哈片刻

2022-09-17 01:48:02

2824 瀏覽

分享至

今天的標題可能會讓人很困惑，明明JavaScript就提供了Math.random()，現成的亂數產生器為什麼放著不用，要自己瞎搞一個出來？

九成以上的遊戲都藉助亂數產生器的幫助，用以建立關卡、棋局、玩家配對、怪物布署、特效動畫等，不管你的下一個遊戲是什麼類型，多少都會在遊戲中加點亂數調味，讓遊戲玩起來更有變化、更不可預測，或至少看起來更活潑不死板。

的確，如果只是想要讓動畫特效看起來沒那麼罐頭，那麼Math.random()就綽綽有餘了。但如果亂數是作為產生棋局、角色屬性、機關參數等影響公平競爭或遊戲玩法的重要角色，那麼自製亂數產生器就有它的好處了。

什麼是亂數產生器

先定義一下這邊講的亂數產生器是什麼東西。

電腦中其實無法真的產生電腦自己都無法預測的亂數，也就是說，只要給定同樣的計算參數，那麼亂數產生器產生的一連串數列都會是一樣的。實際在使用亂數產生器產生亂數時，我們可能會用目前的系統時間，或是玩家的滑鼠位置等較難預知的數字，來當作亂數產生器的參數，這個參數一般被稱為亂數種子(seed)。

亂數產生器的寫法有很多種，有些著重在速度與效率，有些則把重點放在安全性。會有安全性的顧慮，是因為既然亂數是由數學式計算出來的，那麼就有可能在亂數產生一串數列之後，發生數字順序重覆發生的周期性問題。想想看，如果有玩家有辦法藉由觀察一串亂數的順序，進而預測接下來會出現什麼數字，那這遊戲還有公平性可言嗎？就像幾年前被爆出來的寶可夢孵蛋規則，以及魔物獵人洗珠子的漏洞，再大的遊戲公司，若不小心設計，都可能受害於周期不夠長的亂數產生器。

為什麼要自己寫

自己寫亂數產生器的好處可說是一言難盡，就像有人問你為什麼角色的血量不直接宣告成數字(number)，還要特意先寫個Hp的類別(class)，再把Hp裏面的數值拿出來加加減減？為什麼呀？因為要他的可擴充性啊，寶貝。也許以後Hp需要加密，也許Hp的單位要從數值改成百分比，也許Hp要改成能夠容忍一個範圍內的負值...一言難盡啊，是吧！

雖然一言難盡，但小哈還是在這裏舉一些例子，讓同學們感受一下。

可驗證性

在多人遊戲中，如果一開始我們就把亂數產生器的種子同步給所有玩家，那麼之後產生的亂數就有辦法被驗證。

比如說小明施展了一招魔法，配合亂數產生器計算出魔法造成的傷害，然後把這個傷害同步給其他玩家。這時候，小美的電腦收到了這個訊號，電腦隨即用她的亂數產生器，看看這招魔法造成的傷害是不是和我的亂數產生器算出來的一樣，如果發現數字不一樣，那就表示在資料傳遞的過程中，可能被人動了手腳。

遊戲可重播

遊戲中如果用到大量的亂數，那麼若是想在往後提供重播的功能，就需要把遊戲過程中產生的所有亂數都存起來，在重播回放時拿出來用。

但是如果遊戲使用的亂數，是由自己寫的亂數產生器製造的，那麼儲存遊戲時只需要儲存這場遊戲用的亂數種子，在回放時，只要把同樣的亂數種子放入亂數產生器去製造亂數，那麼看起來就會像重播一樣。

使用彈性

遊戲中可能有些時候需要的只是效率高的亂數產生器，安全什麼的不重要，像是節奏很快的槍戰遊戲或格鬥遊戲。但也可能有些時候需要的是安全性高，不可預測的亂數產生器，用來處理棋類遊戲或抽卡機制的工作。

自己寫亂數產生器，就能知道實際亂數產生的原理和過程，方便配合不同的情境使用。如果未來產生亂數的演算法出了問題要升級，也不會受限於系統，而能有更大的彈性。

亂數演算法

亂數產生器當然不能自己亂寫。產生亂數的演算法在網路上有很多可以選，不過一定要挑選那些經過多年驗證沒問題的來用。男怕入錯行，女怕嫁錯郎，亂數就怕跟錯網。

一般亂數產生器是利用幾個非常大的質數，去做加減乘除取餘數，比如以下的函式就是一個早期曾被大量使用的亂數演算法。

class RandomGeneratorOld {
    // 建構子要給一個亂數種子
    constructor(public seed: number) {

    }
    
    /** 取下一個亂數 */
    next(): number {
        // 用質數進行運算，只留最後兩個byte的計算結果
        this.seed = (this.seed * 7919 + 1) & 0xFFFF;
        // 回傳一個介於０到１的亂數
        return this.seed / (0xFFFF + 1);
    }
}

上面舉的例子中使用的質數不是很大，好處是在運算的過程不會溢位，幾乎任何語言環境都可以用，但缺點就是被發現循環數列的機率比較高。

Lehmer亂數演算法

Lehmer亂數產生器是由數學家D.H Lehmer於1949年提出，後來被廣泛應用在電腦的各個領域，是一個運算簡單的數學式。
$R_{k+1} = ( a \cdot R_{k} ) % m$
數列的第一個數字R₀就是亂數種子，有了亂數種子就能夠由上面的式子計算出接在後面的R₁、R₂、R₃、R₄等一串數列。式子中的m要是一個質數或是質數的某個次方，而a必須是m的原根(Primitive root modulo n)。

演算法中使用越大的質數作為m值，越不容易產生循環數列。至於能用到多大的質數，那要看每個語言或執行程式的環境限制。1988年，Park與Miller在他們的論文中建議取第八個梅森質數，也就是２的３１次方減１(2,147,483,647)，套入Lehmer亂數演算法產生亂數。

class RandomGenerator {
    // 建構子要給一個亂數種子
    constructor(public seed: number = 0) {

    }
    
    /** 取下一個亂數 */
    next(): number {
        /** seed不可以等於0，不然後面算出來的都只會是0無限循環 */
        if(this.seed == 0) {
            // 如果seed是０，就用一個自訂的種子
            this.seed = 123456789;
        }
        // 用質數進行運算（Lehmer亂數演算法）
        this.seed = (this.seed * 16807) % 2147483647;
        // 回傳一個介於０到１的亂數
        return this.seed / 2147483647;
    }
}

Lehmer數學式配上梅森質數的亂數演算法，成為一個被廣泛使用的亂數產生器。有了這個基本的亂數產生器幫忙產出介於０到１的隨機數字，之後就方便設計更多和亂數相關的功能。

比如我們可以寫一個產出一串亂碼的函式，用來當作遊戲中各物件的ID代碼。

// 先定義有哪些字元可以拿來用
let charsAllowed = "abcdefghijklmnopqrstuvwxyz0123456789";

/** 使用rng產生length長度的亂碼 */
function randomString(rng: RandomGenerator, length: number): string {
    // 建立一個準備要回傳的字串
    let str = "";
    // 如果字串長度不足length，就要再加一個亂數字元
    while(str.length < length) {
        // 在charsAllowed中隨機選一個位置
        let index = Math.floor(rng.next() * charsAllowed.length);
        // 取出charsAllowed在index上的字元
        let nextChar = charsAllowed.charAt(index);
        // 將取出的字元加到最後結果的後面
        str += nextChar;
    }
    return str;
}

今天就先介紹到這兒。過兩天還會有亂數產生器的延伸議題要和大家研究，敬請期待。